package com.gofaraway.service.左神算法课.tree;

import java.util.HashMap;

/**
 * 根据前序与中序遍历序列构造二叉树
 *
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 *
 * https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150
 * @author ChenPeng
 * @Date 2025/1/9 22:43
 */
public class Code05_ConstructBinaryFromPreorderAndInorder {


    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }



    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }

        HashMap<Integer, Integer> valIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            valIndexMap.put(inorder[i], i);
        }

        return g(preorder, 0, preorder.length -1, inorder , 0, inorder.length -1, valIndexMap);
    }

    private TreeNode f(int[] pr, int L1, int R1, int[] in, int L2, int R2) {
        if (L1 > R1) {
            return null;
        }
        TreeNode head = new TreeNode(pr[L1]);

        //找到头节点在中序 中的位置
        int find = L2;
        while (in[find] != head.val) {
            find++;
        }

        TreeNode leftNode = f(pr, L1 +1, find - L2 + L1, in, L2, find);
        TreeNode rightNode = f(pr, find - L2 + L1 + 1, R1 , in, find +1, R2);
        head.left = leftNode;
        head.right = rightNode;
        return head;
    }


    /**
     * 做一个字典优化
     */
    private TreeNode g(int[] pr, int L1, int R1, int[] in, int L2, int R2,HashMap<Integer, Integer> valIndexMap) {
        if (L1 > R1) {
            return null;
        }
        TreeNode head = new TreeNode(pr[L1]);

        //找到头节点在中序 中的位置
        int find = valIndexMap.get(pr[L1]);

        TreeNode leftNode = g(pr, L1 +1, find - L2 + L1, in, L2, find, valIndexMap);
        TreeNode rightNode = g(pr, find - L2 + L1 + 1, R1 , in, find +1, R2, valIndexMap);
        head.left = leftNode;
        head.right = rightNode;
        return head;
    }


}
